package leetcode;

/**
 * Created with IntelliJ IDEA.
 * User: Ghost
 * Date: 14-6-12
 * Time: 下午4:45
 * To change this template use File | Settings | File Templates.
 */
public class Climbing_Stairs {
//   递归超时
    /*public int climbStairs(int n) {
        if(n==1){
            return 1;
        }
        else if(n==2){
            return 2;
        }
        else{
            return climbStairs(n-1)+climbStairs(n-2);
        }
    }*/
    public int climbStairs(int n){   //记录每一步的过程
        int[] f = new int[n+1];
        f[0] = f[1] = 1;
        for(int i=2;i<=n;i++){
            f[i] = f[i-1] + f[i-2];
        }
        return f[n];
    }
    public static void main(String[] args){
        Climbing_Stairs climbing_stairs = new Climbing_Stairs();
        System.out.println(climbing_stairs.climbStairs(46));
    }
}
